package leetcode_题库;

/**
 * Created by IntelliJ IDEA.
 *
 * @Author : Ding
 * @create 2022/9/20 15:14
 */
public class _55_跳跃游戏 {
    public static void main(String[] args) {
        int[] nums = new int[]{5, 9, 3, 2, 1, 0, 2, 3, 3, 1, 0, 0};
        System.out.println(canJump(nums));
    }

    private static boolean canJump(int[] nums) {
        if (nums.length <= 1) {
            return true;
        }
        //定义最大覆盖范围
        int coverRange = 0;
        for (int i = 0; i <= coverRange; i++) {
            //最大覆盖范围赋值和最新覆盖范围大小进行比较
            coverRange = Math.max(coverRange, i + nums[i]);
            //覆盖到尾巴，就true
            if (coverRange >= nums.length - 1) {
                return true;
            }
        }
        return false;
    }

    public static boolean canJumpFuck(int[] nums) {
        if (nums.length <= 1) {
            return true;
        }
        int i = 0;
        while (i < nums.length - 1) {
            System.err.println(nums[i]);
            if (nums[i] == 0) {
                return false;
            }
            if (nums[i] >= nums.length - i - 1) {
                //如果当前能直接跳到终点，则true
                return true;
            }
            //不能直接跳到终点，找一个最大值当跳板，***废了！
            int index = i + 1;
            for (int j = i + 1; j <= i + nums[i]; j++) {
                if (nums[j] > nums[index]) {
                    index = j;
                }
            }
            i = index;
        }
        return i == nums.length - 1;
    }

}
